package 力扣.链表;

import javax.management.ListenerNotFoundException;

//Definition for singly-linked list.
class ListNode2 {
    int val;
    ListNode2 next;
    ListNode2(int x) { val = x; }
}
public class 分隔链表86 {
    public static void main(String[] args) {
        ListNode2 l1=new ListNode2(1);
        l1.next=new ListNode2(4);
        l1.next.next=new ListNode2(3);
        l1.next.next.next=new ListNode2(2);
        l1.next.next.next.next=new ListNode2(5);
        l1.next.next.next.next.next=new ListNode2(2);
        l1 = partition2(l1, 3);
        while (l1!=null){
            System.out.print(l1.val+" ");
            l1=l1.next;
        }
    }
    public static ListNode2 partition(ListNode2 head, int x) {
        ListNode2 p=new ListNode2(0);
        p.next=head;
        ListNode2 pg=null;
        while (p.next != null){
            ListNode2 first=p;
            if (p.next.val>x){
                pg=p;
            }
            if (p.next.val<x){
                if (pg!=null){
                    ListNode2 p3=p;
                    if (p3.next.next != null){
                        ListNode2 pg2=pg;
                        ListNode2 p4=p3.next.next;
                        pg2.next=p3.next;
                        p3.next.next=pg.next;
                        p3.next=p4;
                    }else{
                        ListNode2 pg2=pg;
                        pg.next=p3.next;
                        p3.next.next=pg2.next;
                    }

                }
            }
            p=p.next;
        }
      return head;
    }

    /**
     * 双向链表，一个链表保存大于x的值，一个链表保存小于x的值
     * @param head
     * @param x
     * @return
     */
    public static ListNode2 partition2(ListNode2 head, int x) {
       ListNode2 largeLiNode=new ListNode2(0);
       ListNode2 large=largeLiNode;
       ListNode2 smallLiNode=new ListNode2(0);
       ListNode2 small=smallLiNode;
       while (head != null){
           int val= head.val;
           if (val>=x){
               large.next=head;
               large=large.next;
           }else{
               small.next=head;
               small=small.next;
           }
           head=head.next;
       }
       large.next=null;//因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用
       small.next=largeLiNode.next;//这里也同样切断这个引用
      return smallLiNode.next;
    }
}
